package P1线性结构.LeetCode单调栈与单调队列;

import java.util.ArrayDeque;

public class LC402 {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < num.length(); i++) {
            char digit = num.charAt(i);
            while (!stack.isEmpty() && k > 0 && digit < stack.peekLast()) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(digit);
        }
        for (int i = 0; i < k; i++) {
            stack.pollLast();
        }
        StringBuilder sb = new StringBuilder();
        boolean flag = true;    //假设有前导零
        while (!stack.isEmpty()) {  //001012
            char digit = stack.pollFirst();
            if (flag && digit == '0') {
                continue;
            }
            flag = false;
            sb.append(digit);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}